"""
在无限的整数序列1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...中找到第n 位数字。
注意：n是正数且在 32 位整数范围内（n < 231）。
示例 1：
输入：3
输出：3

示例 2：
输入：11
输出：0
解释：第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 0 ，它是 10 的一部分。

链接：https://leetcode-cn.com/problems/nth-digit
"""


class Solution:
    def findNthDigit(self, n: int) -> int:
        indexCount = 9  # 当前的数字长度，区间的数字个数
        numLen = 1  # 数字的长度
        while indexCount * numLen < n:
            n -= indexCount * numLen  # 减去当前这个长度所占的位数
            numLen += 1
            indexCount *= 10

        indexCount //= 9  # 比如是10000
        targetNum = indexCount + (n - 1) // numLen  # 第n位所在的那个数字
        idx = (n - 1) % numLen  # 第n为是在那个数字的第idx位
        return int(str(targetNum)[idx])


if __name__ == "__main__":
    A = Solution()
    nums = 137
    print(A.findNthDigit(nums))

    # A = Solution3()
    # nums = [ 7]
    # target = 7
    # print(A.search(nums, target))
